//Mon Oct  3 00:08:09 PDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ShortPalindromes {

	public String[][] dp;
	public String str;

	public String shortest(String base) {
		str = base;
		dp = new String[str.length() + 1][str.length() + 1];
		return solve(0, str.length());
	}

	public String solve(int left, int right) {
		if (left + 1 >= right)
			return str.substring(left, right);
		if (dp[left][right] != null)
			return dp[left][right];
		if (str.charAt(left) == str.charAt(right - 1))
			return dp[left][right] = str.charAt(left)
					+ solve(left + 1, right - 1) + str.charAt(left);
		String s1 = str.charAt(left) + solve(left + 1, right)
				+ str.charAt(left);
		String s2 = str.charAt(right - 1) + solve(left, right - 1)
				+ str.charAt(right - 1);
		if (s1.length() < s2.length())
			return dp[left][right] = s1;
		else if (s1.length() > s2.length())
			return dp[left][right] = s2;
		else if (s1.compareTo(s2) < 0)
			return dp[left][right] = s1;
		else
			return dp[left][right] = s2;
	}

	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
